模拟退火算法的Python实现（非线性函数优化为例）

2023-11-19 04:41| 来源: 网络整理| 查看: 265

1、模拟退火算法（SA）介绍

模拟退火算法(Simulated Annealing，SA)是一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

（一）算法流程：

在这里插入图片描述（二）Metropolis准则：

在这里插入图片描述 Metropolis准则用于判断是否接受新解。模拟退火中函数最优化的过程是f值不断降低的过程，但为了跳出局部最优解，当函数值变大时也以一定概率接受，且这个概率随着温度T的降低而变小，最终变化趋于稳定，这也是模拟退火的核心思想。

（三）非线性函数优化中扰动产生新解的过程

在非线性函数优化中，如何产生新的一组解是重要的问题，由于不能像TSP（旅行商）问题那样用多元置换、互换等方式简单产生新解，所以在这里我们将扰动与模拟退火的思想结合，扰动产生新解的幅度由系统温度决定，得到公式如下：

x1 = x + T ∗ R（R∈[−1,0)∪(0,1]）

其中，T为当前温度，R为[-1, 1]间不为零的一个随机数，以此公式来产生新解，并且随着温度的下降，新解的扰动幅度也会减小，最终趋于稳定。

2、Python实现（非线性函数优化为例）

（1）定义待优化函数

在这里插入图片描述

其中，x∈[0,10]，y∈[0,10] import math def func(x, y): num = 6.452 * (x + 0.125 * y) * (math.cos(x) - math.cos(2 * y)) ** 2 den = math.sqrt(0.8 + (x - 4.2) ** 2 + 2 * (y - 7) ** 2) return - (num / den + 3.226 * y) 由于要求该函数的最大值，而模拟退火中求得的是目标函数的最小值，所以需要在函数前加上负号

（2）初始化SimulateAnnealing类

class SimulateAnnealing: def __init__(self, func, iter=10, T0=100, Tf=1e-8, alpha=0.99): """ Annealing parameters :param iter: Number of internal cycles :param T0: Initial temperature :param Tf: Final temperature :param alpha: Cooling factor """ self.func = func self.iter = iter self.alpha = alpha self.T0 = T0 self.Tf = Tf self.T = T0 self.x = [random() * 10 for i in range(iter)] self.y = [random() * 10 for i in range(iter)] self.history = {'f': [], 'T': []} iter：内循环迭代次数，目的是基于不同初值进行多次退火，避免陷入局部最优T0：初始温度，可以根据解的约束条件等适当进行调整Tf：温度终值，一般可以取1e-8、1e-13等较小的值，目的是降低收敛速度，提高精确度alpha：降温系数，一般取0.99，目的同上

（3）扰动产生新解的过程

def generate_new(self, x, y): while True: x_new = x + self.T * (random() - random()) y_new = y + self.T * (random() - random()) if (0

【本文地址】

公司简介

联系我们